package com.singzi.leetcode.jianzhiOffer;

import java.util.HashSet;

public class T0049 {
    public static void main(String[] args) {
        Solution0049 solution0049 = new Solution0049();
        solution0049.nthUglyNumber(20);
    }
}
class Solution0049 {
    public int nthUglyNumber(int n) {
        if(n <= 6 ) return n;
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        int maxValue = Integer.MAX_VALUE;
        int cont = 5;
        for(int i = 6;i <= maxValue;i++){
            for(int j = 2;j <= Math.sqrt(i);j++){
                if(i % j == 0){

                    if(set.contains(j) && set.contains(i/j)){
                        set.add(i);
                        cont++;
                        if(cont == n) return i;
                        break;
                    }
                }
            }
        }
        return 0;
    }
}